package comeback.sort;


public class QuickSort {
    public static void main(String[] args) {
        int[] num = new int[]{3,2,9,7,1,5,4};
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(num, 0, num.length - 1);
        for (int i : num) {
            System.out.println(i);
        }
    }

    public void quickSort(int[] num, int left, int right) {
        if (left > right) {
            return;
        }
        int mid = left + (right - left) / 2 ;
        int tmp = num[mid];
        int i = left;
        int j = right;
        while (i < j) {
            // TODO j先写在前面
            while (i < j && num[j] > tmp) {
                j--;
            }
            while (i < j && num[i] < tmp) {
                i++;
            }
            swap(num, i, j);
        }
        // TODO 每次定位一个数据的位置，这个位置是 i
        quickSort(num, left, i - 1);
        quickSort(num, j + 1, right);
    }

    private void swap(int[] num, int left, int right) {
        int tmp = num[left];
        num[left] = num[right];
        num[right] = tmp;
    }
}
